#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <fstream>

// Nick Glyder    Date: 3/27/13
// 
// This program is meant to solve the N-Queens Problem.
// Specifically, it tries to place N Queens on an N x N chessboard such that
// none of the Queens can capture one another. It achieves this using a 
// recurssive backtracking algorithm that tries to find all solutions for
// a given placement on the first Queen in different locations in the first column 
// of the board. Will return K solutions in a visual format.
//
// Update - 2/5/2014
// This program now writes each solution to a file as well as printing to the console.
// This file can be used in conjunction with my NQueens GUI written in Java to view 
// the solutions in a more traditional way. This is done through a simple shell script.

using namespace std;

// Queen struct, essentially an ordered pair
struct Queen{
   int column;
   int row;
};

// Method prototypes
bool inJeopardy(Queen inQuestion, Queen *set, int N, int numPlaced);
void printSolution(Queen *solution, int N, ofstream *out);
void findSolutions(Queen justPlaced, Queen *alreadySet, int N, int K, int numberSet, int & numSolutions, ofstream *out);

// Main method simply checks for adequate command line parameters and reads them in for use.
// Then calls the findSolutions method passing in all possible placements of the first
// Queen in the first column. 
int main(int argc, char*argv[])
{
   int N,                     // Size of N-Queen problem
       K,                     // Number of solutions printed 
       solutionsFound = 0,    // Current # of solutions found
       firstQueenRow = 0;     // Row of the first Queen to be placed
           
   ofstream *solutionFile = new ofstream();
   solutionFile->open("src/queensSolutions.txt");

   // Check for sufficient number of command line arguments
   if(argc < 3)
   {
      cout<<"USAGE: nqueens #_OF_QUEENS #_OF_SOLUTIONS"<<endl;
   }      
   
   sscanf(argv[1],"%d",&N);      //
   sscanf(argv[2],"%d",&K);      // Read Command Line arguments 
   
   Queen solutionSet[N];      // Set of Queens in an arbitrary solution   
     
   cout<<"No more than "<<K<<" solutions to the "<<N<<"-Queen problem if they exist"<<endl;  
     
   // Ask for solutions for a given placement of the first Queen  
   for(firstQueenRow = 0; firstQueenRow < N; firstQueenRow++)
   {
      if(solutionsFound < K)
      {
         Queen firstQueen = {0,firstQueenRow};
         solutionSet[0] = firstQueen;
         findSolutions(firstQueen, solutionSet, N, K, 1, solutionsFound, solutionFile);
      }
   }
     
   solutionFile->close();

   return N;
}

// Given the most recently placed Queen, the set of already placed Queens,
// the size of the problem and the number of already placed Queens, tries to
// find a valid spot in the next column over to place a new Queen
void findSolutions(Queen justPlaced, Queen *alreadySet, int N, int K, int numberPlaced, int & numSolutions, ofstream *out)
{  
   if(numSolutions < K)
   {
   int newColumn = justPlaced.column+1;      // New queen is in the next column over
      
      // Traverses from row 0 to row N-1
      for(int ndx = 0; ndx < N; ndx++)
      {
         Queen nextPlaced = {newColumn,ndx};    // Create a virtual Queen to be placed in the next column
         
         // If this Queen would not be in jeopardy if placed, add it to the set of solution Queens
         // and increment the number of placed Queens
         if(inJeopardy(nextPlaced, alreadySet, N, numberPlaced) == false)
         {
            alreadySet[numberPlaced] = nextPlaced;
            numberPlaced++;
            
            // If we have placed N Queens
            if(numberPlaced == N)
            {
               numSolutions++;
               printSolution(alreadySet,N, out);  // We found a valid solution
               return;                       // Break recurssive loop
            }// if
            
            // Queen is validly placed, but not the last Queen
            // When the recurssive call returns, we have to backtrack, so decrement
            // the number of valid Queens
            else
            {
               findSolutions(nextPlaced, alreadySet, N, K, numberPlaced, numSolutions, out);
               numberPlaced--;                                          
            }// else
         }// if(notInJeopardy)
      
      }// for(ndx)
   }// if(numSolutions)

}// findSolutions()

// Check if a Queen we are trying to set would be in jeopardy from any other Queen
// Requires the length of alreadySet (numPlaced) because recursive 
// calls could leave some Queens in the set that we don't want to check
bool inJeopardy(Queen inQuestion, Queen *alreadySet, int N, int numPlaced)
{
   // for every valid Queen in alreadySet
   for(int x = 0; x < numPlaced; x++)
   {
      // If there is a match in column or row with the Queen inQuestion, we have a conflict
      if(inQuestion.row == alreadySet[x].row || inQuestion.column == alreadySet[x].column)
      {
         return true;   // inQuestion in jeoaprdy
      }
      
      int offSet = 1;
      
      // Now check the diagonals originating on the Queen inQuestion
      // Doesn't matter if we go out of bounds of the board, but we have to be sure 
      // to hit every part of the diagonal in the case that inQuestion is in a corner
      while(offSet < N)
      {
         if(inQuestion.row + offSet == alreadySet[x].row && inQuestion.column + offSet == alreadySet[x].column)
            return true;   // inQuestion in jeoaprdy
         if(inQuestion.row + offSet == alreadySet[x].row && inQuestion.column - offSet == alreadySet[x].column)
            return true;   // inQuestion in jeoaprdy
         if(inQuestion.row - offSet == alreadySet[x].row && inQuestion.column + offSet == alreadySet[x].column)
            return true;   // inQuestion in jeoaprdy
         if(inQuestion.row - offSet == alreadySet[x].row && inQuestion.column - offSet == alreadySet[x].column)
            return true;   // inQuestion in jeoaprdy
            
         offSet++;
      }
   }
   return false;  // Safe to place inQuestion
}

//Prints a visual representation of a given solution to an N-queen problem
void printSolution(Queen *solution, int N, ofstream *out)
{
   bool foundQueen = false;         // Keeps track of whether a Queen needs to be printed

   for(int column = 0; column < N; column++)    // Traverse from column 0 to N-1
   {
      for(int row = 0; row < N; row++)          // Traverse from row 0 to N-1
      {
         foundQueen = false;                    // Resets Queen tracker
         for(int ndx = 0; ndx < N; ndx++)       // Traverses solution set of Queens
         {
            // If the current position matches that of any queen in the set, print "Q"
            if(solution[ndx].column == column && solution[ndx].row == row)
            {
               cout<<"Q ";
	       *(out)<< '1';
               foundQueen = true;
            }
         }// for(ndx)
      if(foundQueen == false){ cout<<"_ "; *(out)<<'0';}   // If we didn't find any Queens to print, print a "_"
      }// for(row)
      cout<<endl;
      *(out)<<endl;
   }// for(column)
   
   cout<<"-------------------"<<endl;
   *(out)<<endl;
   
}// printSolution()
